by Μπαζ.

Δομή Γλωσσών Προγραμματισμού

Η δομή των Γλωσσών Προγραμματισμού ορίζεται σε 3 επίπεδα:

• Λέξεων: πως οι χαρακτήρες σχηματίζουν στοιχειώδεις λεξικές μονάδες - lexemes
• Σύνταξης: πως συνδιάζονται σε πρόγραμμα τα διάφορα είδη φράσεων
• Συμφραζόμενων: πχ. ποιά ονόματα μεταβλητών είναι ενεργά σε ποιά σημεία, εγκυρότητα τύπων, κλπ...

Λεξική Δομή

Αφορά:

• Αναγνωρηστικά
• Λεξικές μονάδες

Αλφάβητο Γλωσσών Προγραμαμτισμού

• Το σύνολο έγκυρων χαρακτήρων που μπορούν να χρησιμοποιηθούν σε μία γλωσσών προγραμματισμού
  • Για το μεταγλωττιστή κάθε χαρακτήρας αντιστοιχεί σε μία μοναδική τιμή (ASCII, UTF-16, κλπ..)
  • Κάποιες γλώσσες διακρίνουν πεζά-κεφαλαία

Δεσμευμένες Λέξεις - Λέξεις Κλειδιά

• Δεσμευμένες Λέξεις: κανένα όνομα στο πρόγραμμα δεν μπορεί να είναι ίδιο με αυτές

• Λέξεις Κλειδιά: Λέξεις με ειδική σημασία στη γλώσσα (όχι απαραίτητα δεσμευμένες)

• Συχνά ταυτίζονται ή οι λέξεις κλειδιά είναι υποσύνολο των δεσμευμένων

• Μπορεί επίσης να υπάρχουν ονόματα που χρησιμοποιούνται από άλλα κομμάτια του προγράμματος (πχ. βιβλιοθήκες), αλλά η χρήση τους περιορίζεται από το μεταφραστή και όχι από την ίδια τη γλώσσα, οπότε δεν ταυτίζονται με τις παραπάνω κατηγορίες

Ονόματα

• Ονόματα: χρησιμοποιούνται για την ταυτοποίηση μεταβλητών, τύπων, ετικετών, διαδικασιών, πακετών και άλλων οντοτήτων
  • Συνήθως επιβάλλονται περιορισμοί στη μορφή τους (πχ. να μην ξεκινούν από αριθμό)
• Είναι αναγνωρηστικά μεταβλητού μήκους
  • Ο διαχωρισμός τους ακολουθεί την ταύτηση για τη λεξική μονάδα μεγαλύτερου δυνατού μήκους
    • δλδ. ως όνομα αναγνωρίζεται πάντα η μεγαλύτερη δυνατή συμβολοσειρά, χωρίς κενά, με ένα μόνο αναγνωριστικό
    • πχ. η λέξη doif δεν ταυτίζεται με τις λέξεις κλειδιά do και if, αλλά ως ένα όνομα

Τελεστές

• Τελεστές: λεξικές μονάδες που συμπεριφέρονται γενικά σαν συναρτήσεις, αλλά διαφέρουν συντακτικά και σημασιολογικά

  • αριθμητικοί
  • σύγκρισης
  • λογικοί
  • ανάθρσης
  • επιλογής πεδίου σε record (.)
  • ανάλυσης εμβέλειας (::)
• Η κάθε γλώσσα ορίζει σύνολο ενσωμματωμένων τελεστών, και κάποιες φορές δίνει τη δυνατότητα στους προγραμματιστές

  • να τους υπερφορτώσουν
  • να ορίσουν καινούργιους

Διαχωριστές και Κενά

• Διαχωριστές ή κενά: χαρακτήρες που όταν διαβάζονται, επιβάλλουν την απόσπαση αναγνωρηστικών από το υπόλοιπο κείμενο
• Στις περισσότερες γλώσσες, οι λεξικές μονάδες διαχωρίζονται με ένα πλό κενό
• Όλες οι γλώσσες διαθέτουν χαρακτήρες με σημασία
  • διαχωρισμού εντολών
  • τερματισμού εντολών
  • συνέχισης σε νέα γραμμή

Κυριολεκτικές Σταθερές

• Κυριολεκτικές σταθερές: αναπαριστούν σταθερές τιμές, σε αντίθεση όμως με τις (ορισμένες) σταθερές, μπορούν να έχουν μόνο μία τιμή
  • Συνήθως χρησιμοποιούνται στην αρχικοποίηση μεταβλητών
  • πχ 14, 0.5, "hello", κλπ...

Σχόλια

Διακρίνονται σε:

• inline και block
• Αυτά που αγνωούνται τελείως και αυτά που έχουν κάποια σημασία
• Υποστηριζουν ένθεση ή όχι

Συντακτικό Γλωσσών Προγραμματισμού

Τα βασικά συντακτικά μέρη των προγραμμάτων είναι:

• Εκφράσεις: υπολογισμοί που καθορίζουν τις τιμές τους. Αν μία έκφραση αλλάζε τη συμπεριφορά του προγράμματος, λέμε ότι συνοδεύεται από παρενέργειες
• Εντολές: οδηγίες που αλλάζουν ρητά τη συμπεριφορά του προγράμματος
  • πχ. x = x + 3, αλλάζει την τιμή της μεταβλητής χ
• Δηλώσεις: εισάγουν νέα ονόματα και ορίζουν τις ιδιότητές τους

Για τον ορισμό των συντακτικών δομών των γλωσσών προγραμματισμού χρησιμοποιούνται Γραμματικές Χωρίς Συμφραζόμενα (δες παρακάτω)

Σύνταξη Προστακτικών και Δηλωτικών Γλωσσών

• Στις προστακτικές γλώσσες προγραμματισμού τα προγράμματα αποτελούνται από ακολουθίες εντολών που:

  • εκτελούν υπολογισμούς
  • αναθέτουν τιμές σε μεταβλητές
  • δέχονται είσοδο ή παράγουν έξοδο
  • εκτρέπυν το έλεγχο σε κάποιο άλλο σημείο της ακολουθίας
• Τα βασικά στοιχεία στις προστακτικές γλώσσες είναι

  • εντολές ανάθεσης
  • επαναληπτικοί βρόγχοι
  • ακολουθίες (blocks) εντολών
  • διαδικασίες
  • υποθετικές εντολές
  • εντολές διαχείρησης εξαιρέσεων
• Στις συναρτησιακές γλώσσες προγραμματισμού, η εκτέλεση γίνεται συνήθως με υπολογισμό τιμής εκφράσεων που περιέχουν συναρτήσεις

• Υπάρχουν και γλώσσες με συνδυασμό προστακτικών και δηλωτικών δομών

Σημασία Γλωσσών Προγραμματισμού

• Αναφέρεται σε πληροφορίες σχετικές με τη συμπεριφορά και τα αποτελέσματα εκτέλεσης ενός προγράμματος

  • Σε αντίθεση με τη σύνταξη που αναφέρεται στην έγκυρη δομή προγραμμάτων
• Ένα πρόγραμμα μπορεί να είναι συντακτικά ορθό αλλά σημασιολογικά λάθος (εμφανίζει λάθη σε σχέση με τη σημασία της γλώσσας)

• Ένα πρόγραμμα μπορεί να είναι σημασιολογικά ορθό, αλλά λογικά λάθος (δεν ταιριάζει με τους στόχους του προγραμματιστή)

• Ο ορισμός της σημασίας είναι πιο δύσκολος από τον ορισμό της σύνταξης (μπορεί να περιέχει ασάφιες)

  • Εγχειρίδιο Αναφοράς της Γλώσσας Προγραμματισμού: Φυσική γλώσσα, ασαφές, ανακριβές, ελλειπές
  • Προδιαγραφή και Ανάπτυξη Μεταφραστή: Απαντά όλα τα ζητήματα σε σχέση με τη σημασία, αλλά επηρεάζεται από λάθη και εξαρτήσεις μηχανής εκτέλεσης
  • Τυπικός Ορισμός: μαθηματικές μέθοδοι

Ιδιότητες Και Συνδέσεις

• Ιδιότητα: κανόνας σημασίας ονομάτων

  • μεταβλητών
  • σταθερών
  • διαδικασιών
• πχ.

  • θέση: περιοχή μνήμης (αφαιρετική θεώρηση διευθυνσιοδότησης, ξεκινάμε από το 0)
  • τιμή: η αποθηκευμένη ποσότητα
• Σύνδεση (binding): Η συσχέτιση μίας ιδιότητας με ένα όνομα

• Δηλώσεις: συντακτικά στοιχεία που συνδέουν ονόματα σε ιδιότητες

Παράδειγμα

• Εντολές: μπορούν επίσης να συνδέσουν νέες ιδιότητες ή να αλλάξουν υπάρχουσες

Παράδειγμα

• Συνδέσεις σε διαφορετικές γλώσσες

  • Στις καθαρά συναρτησιακές η τιμή συνδέεται σε όνομα μόνο μία φορά και δεν χρειάζεται διαφορετική σύνδεση θέσης, αφού η τιμή δεν αλλάζει
  • Σε πιο δυναμικές γλώσσες, το όνομα μπορεί αν συνδέεται κατά την εκτέλεση με σειρά από διαφορετικές τιμές
• Χρόνος Σύνδεσης (binding time): η χρονική στιγμή υπολογισμού και σύνδεσης ιδιότητας σε όνομα

  • Ανάλογα με το χρόνο σύνδεσης διακρίνουμε
    • Στατικές Συνδέσεις: πριν την εκτέλεση (στατικές ιδιότητες)
    • Δυναμικές Συνδέσεις: κατά την εκτέλεση (δυναμικές ιδιότητες)
  • Διαφορετικές γλώσσες είναι πιο κατάλληλες για την κάθε κατηγορία
    • Οι συναρτησιακές στηρίζουν περισσότερο τη δυναμική σύνδεση από τις προστακτικές
    • Οι μεταγλωττιστές στηρίζουν περισσότερο στατικές από τους διερμηνευτές

Στατικές Συνδέσεις

• Συμβαίνουν κατά την:

  • Συντακτική ή σημασιολογική ανάλυση (Χρόνος Μετάφρασης)
  • Διασύνδεση προγράμματος με βιβλιοθήκες (Χρόνος Διασύνδεσης)
  • Φόρτωση προγράμματος στη μνήμη για εκτέλεση (Χρόνος Φόρτωσης)
  • Κάποιες φορές και πριν από τη μετάφραση, κατά τον ορισμό της γλώσσας
• Ο μεταφραστής δημιουργεί μία δομή δεδομένων στην οποία διατηρεί τις συνδέσεις, τον πίνακα συμβόλων

• Μπορεί να αναπαρασταθεί ως μία συνάρτηση που εκφράζει τη σύνδεση ιδιοτήτων σε ονόματα

  • Ο ορισμός της συνάρτησης αλλάζει καθώς εξελίσσεται η μετάφραση, ανάλογα με τη δημιουργία και τη διαγραφή συνδέσεων
• Στη στατική σημασιολογική ανάλυση καθορίζονται οι ιδιότητες ονομάτων που εμφανίζονται σε δηλώσεις και επιβεβαιώνεται πως η χρήση τους συμμορφώνεται με τις δηλωμένες ιδιότητες

Δυναμικές Συνδέσεις

• Συμβαίνουν κατά την:

  • Είσοδο/Έξοδο από συναρτήσεις
  • Είσοδο/Έξοδο από το πρόγραμμα
• Κατά την εκτέλεση παράγεται κώδικας (από το μεταγλωττιστή) που διατηρεί πληροφορίες για τις ιδιότητες ονομάτων, όπως θέσεις και τιμές, κατά την εκτέλεση

• Το μέρος που συνδέει τις ιδιότητες θέσης με ονόματα, ονομάζεται περιβάλλον

• Το μέρος που συνδέει τις ιδιότητες τιμής με θέσεις, ονομάζεται μνήμη

Ρητές και Έμμεσες Συνδέσεις

• Σε μία δήλωση οι συνδέσεις μπορεί να καθορίζονται
  • ρητά: από τον προγραμματιστή
  • έμμεσα: από τους κανόνες της γλώσσας
• Η ίδια σύνδεση μπορεί να γίνει και ρητά και έμμεσα ανάλογα με το πηγαίο πρόγραμμα
• Σε κάποιες γλώσσες μία απλή αναφορά σε όνομα, προκαλεί τη δήλωσή της (συνήθως σε μία εντολή ανάθεσης)
• Στις C/C++ έχουμε ορισμούς, δηλώσεις που συνδέουν όλες τις σχετικές ιδιότητες ενός ονόματος
• Σε γλώσσες με δυναμικούς τύπους, τα ονόματα έχουν μόνο σύνδεση τιμής, ενώ οι ιδιότητες τύπων συνδέονται με τις ίδιες τις τιμές

Blocks

• Συντακτικές δομές που αποτελούνται από μία αλληλουχία δηλώσεων, ακολουθούμενη από μία αλληλουχία εντολών
  • Η αλληλουχία εντολών περικλείεται συνήθως από στοιχεία σύνταξης όπως '{' και '}' ή 'begin' και 'end'
• Στη C τα blocks ονομάζονται και σύνθετες εντολές, και εμφανίζονται στο σ΄σμα συναρτήσεων, σε ορισμούς συναρτήσεων και σε θέση οποιασδήποτε εντολής
• Στη C η θέση μίας δήλωσης σε σχέση με ένα block, την κατηγοριοποιεί ως
  • Τοπική όταν σχετίζεται με ένα συγκεκριμένο block
  • Μη Τοπική (εξωτερική ή καθολική) όταν συμβαίνει εκτός του block

Παράδειγμα

• Μπορούμε επίσης να έχουμε ένθεση ενός block σε ένα άλλο, σε οποιοδήποτε βάθος
  • Τα ίδια ονόματα μπορούν αν δηλώνονται ξανά σε ένθετα blocks
  • Κάθε νέο όνομα που δηλώνεται το συσχετίζουμε με μία λεξική διεύθυνση, δλδ ένα ζεύγος αριθμών που αποτελείται από
    • τον αριθμό επιπέδου: ξεκινάει από το 0 στο εξωτερικό επίπεδο και αυξάνεται κατεβαίνοντας επίπεδα
    • τον αριθμό μετατόπισης: ξεκινάει από το 0 για κάθε block και αυξάνεται για κάθε όνομα

Παράδειγμα

Structs και Κλάσεις

• Στη C ένας ορισμός struct αποτελείται από δηλώσεις τοπικών μεταβλητών
  • Η σύνταξη μοιάζει με block (άγκιστρα), αλλά στο τέλος έχει ερωτηματικό (σύνθετη δήλωση ?)

Παράδειγμα

• Στις αντικειμενοστρεφείς γλώσσες μπορούμε και να δηλώσουμε κλάσεις
  • Είναι η μόνη δήλωση που δεν χρειάζεται να γίνει μέσα σε άλλη κλάση

Παράδειγμα

Εμβέλεια Συνδέσεων

• Εμβέλεια Σύνδεσης (scope of binding): το μέρος του προγράμματος μέσα στο οποίο διατηρείται μία σύνδεση
  • Εμβέλεια δήλωσης: όρος που χρησιμοποιείται αν όλες οι συνδέσεις μίας δήλωσης έχουν την ίδια εμβέλεια
  • Εμβέλεια ονόματος: όρος που χρησιμοποιείται καταχρηστικά, καθώς το ίδιο όνομα μπορεί να εμφανίζεται σε διαφορετικές δηλώσεις με διαφορετική εμβέλεια για την κάθε μία
• Κανόνας λεξικής εμβέλειας:
  • Σε μία γλώσσα που υποστηρίζει ένθετα blocks, η εμβέλεια μίας σύνδεσης περιορίζεται
    • στο block της σχετικής δήλωσης
    • σε κάθε block που περιέχεται σε αυτό
• Κανόνας δήλωσης πριν τη χρήση:
  • Η εμβέλεια μίας δήλωσης ξεκινά ακριβώς μετά το σημείο της δήλωσης, και τελειώνει στο τέλος του block στο οποίο βρίσκεται

Παράδειγμα

• Οι δηλώσεις σε ένθετα block έχουν προτεραιότητα έναντι των προηγούμενων δηλώσεων

Παράδειγμα

• Στο πράδειγμα λέμε ότι η καθολική δήλωση της x έχει μία τρύπα στην εμβέλεια μέσα στην p, και ότι η τοπική δήλωση της χ βρίσκεται στη σκιά της καθολικής της δήλωσης
  • Η εμβέλεια μπορεί να περιλαμβάνει και τρύπες εμβέλειας: εκεί που οι συνδέσεις εξακολουθούν να υπάρχουν αλλά δεν είναι ορατές
  • η ορατότητα μίας δήλωσης περιλαμβάνει μόνο τα μέρη του προγράμματος όπου η συνδέσεις της δήλωσης εφαρμόζονται
• στη C++, για να προσπελαύνονται κρυμμένες δηλώσεις, διαθέτιε τον τελεστή ανάλυσης εμβέλειας "::"

Εμβέλεια και C

Ιδιότητα Διασύνδεσης και Κλάσεις Αποθήκευσης

• Ένα πρόγραμμα C μπορεί να αποτελείται από πολλά πηγαία αρχεία

  • Ο προεπεξεργαστής ενσωμματώνει τα αρχεία που αναφέρονται στα #include, σχηματίζοντας διαφορετικές μονάδες μεταγλώττισης
• Η ιδιότητα διασύνδεσης εξαναγκάζει ένα όνομα, που δηλώνεται σε περισσότερες από μία εμβέλειες, ή περισσότερες από μία φορά στην ίδια εμβέλεια, να αναφέρεται στην ίδια οντότητα (μεταβλητή, συνάρτηση, struct)
  

• Η εμβέλεια δήλωσης ενός ονόματος επηρεάζεται και από την κλάση αποθήκευσης με την οποία δηλώνεται:

  • extern - προκαθορισμένη κλάση για ονόματα που δε βρίσκονται μέσα σε συνάρτηση και για δηλώσεις συναρτήσεων
  • auto - προκαθορισμένη κλάση για δηλώσεις εντός συνάρτησης
  • static - δηλώνει ότι η μνήμη εκχωρείται άπαξ (μόνο μία φορά)
  • register - δηλώνει ότι μπορεί να αποθηκευτεί σε καταχωριτή αντί για μνήμη
• Αν μία δήλωση είναι μέσα σε συνάρτηση και δεν περιέχει τις λέξεις κλειδιά static ή extern, τότε η μνήμη εκχωρείται και απελευθερώνεται με προσέγγιση λειτουργίας στοίβας

Κανόνες Εμβέλειας

1. Ένα όνομα έχει τοπική εμβέλεια, αν αυτό δηλώνεται σε συνάρτηση ή block, άρα μπορεί να χρησιμοποιηθεί μόνο στο block/συνάρτηση που το περικλείει
2. Τα ονόματα παραμέτρων συνάρτησης έχουν εμβέλεια σε όλο το block με τον κώδικα της συνάρτησης
3. Αν ένα όνομα σε ένθετο block είνα ίδιο με όνομα σε block που το περικλείει, τότε η ένθετη δήλωση, αποκρύπτει την εμβέλεια της δήλωσης του περικλείοντος block
4. Τα ονόματα ετικετών(labels) είναι το μόνα που έχουν εμβέλεια συνάρτησης, δλδ η ετικέτα μπορεί να αναφερθεί σε εντολή goto που μπορεί να βρίσκεται ακόμα κα πριν από τη δήλωσή της
5. Ένα όνομα έχει εμβέλεια αρχείου (καθολική) αν δε δηλώνεται μέσα σε block
6. Για δηλώσεις ονομάτων με εμβέλεια αρχείου, η μνήμη εκχωρείται άπαξ και κλάση αποθήκευσης
   1. την προκαθορισμένη ή auto,
      1. για ονόματα συνάρτησης (δεν μπορούν να είναι auto ή register), η δήλωση έχει το ίδιο επίπεδο διασύνδεσης με οποιαδήποτε άλλη ορατή δήλωση, με εμβέλεια αρχείου για το ίδιο όνομα, αν υπάρχει, αλλιώς εξωτερική διασύνδεση
      2. για ονόματα μεταβλητών, struct, κα. έχουμε εξωτερική διασύνδεση
   2. extern, η δήλωση έχει το ίδιο επίπεδο διασύνδεσης με οποιαδήποτε άλλη ορατή δήλωση, με εμβέλεια αρχείου αν υπάρχει, αλλιώς εξωτερική διασύνδεση
   3. static, η δήλωση έχει εξωτερική διασύνδεση
7. Για δηλώσεις ονομάτων με τοπική εμβέλεια και κλάση αποθήκευσης
   1. την προκαθορισμένη auto ή register ή static, τα ονόματα είναι χωρίς διασύνδεση
   2. extern ισχύουν οι ίδιοι κανόνες για δήλωση με εμβέλεια αρχείου, και κλάση αποθήκευσης extern

Οι κανόνες 5. και 6. περιληπτικά:

• Η μνήμη εκχωρείται άπαξ, για όλες τις δηλώσεις με εμβέλεια αρχείου και τις δηλώσεις extern με τοπική εμβέλεια
• Χωρίς διασύνδεση, οι δηλώσεις τοπικής εμβέλειας, auto, register, static
• Με εξωτερική διασύνδεση όλες οι άλλες, εκτός από
  • Δηλώσεις συναρτήσεων, auto
  • Δηλώσεις extern
  • για τις οποίες υπάρχει ορατή δήλωση με εμβέλεια αρχείου για το ίδιο όνομα -> έχουν ίδια διασύνδεση με τη άλλη δήλωση

Πίνακας Συμβόλων

• Υποστηρίζει την εισαγωγή, αναζήτηση και διαγραφή ονομάτων, μαζί με τις ιδιότητές τους και τις συνδέσεις που υλοποιούν οι δηλώσεις τους
• Επεξεργασία στοίβας των πληροφοριών εμβέλειας, σε γλώσσα με δομή block
  • κατά την είσοδο σε block, όλες οι δηλώσεις του block υποβάλλονται σε επεξεργασία και οι αντίστοιχες συνδέσεις εισάγονται στον πίνακα συμβόλων
  • κατά την έξοδο από block, οι συνδέσεις που δημιουργήθηκαν από τις δηλώσεις αφαιρούνται, αποκαθιστώντας τυχόν προυπάρχουσες συνδέσεις
• Αν ο πίνακας συμβόλων,
  • δημιουργείται κατά τη μεταγλώττιση, παρέχει πληροφορίες για τη στατική εμβέλεια των ονομάτων
  • διαχειρίζεται πληροφορίες κατά την εκτέλεση του προγράμματος, εκφράζει τη δυναμική εμβέλεια των ονομάτων

Παραδείγματα Πινάκων Συμβόλων και Εμβέλειας Ονομάτων

Στατική Εμβέλεια

Παράδειγμα

Δυναμική Εμβέλεια

Παράδειγμα

Σύνθετες Δομές Δεδομένων

Παράδειγμα

Ανάλυση Ονομάτων

• Ανάλυση ονομάτων: η διαδικασία που συσχετίζει κάθε αναφορά ονόματος με τη σωστή δήλωση, σύμφωνα με τη σημασία της γλώσσας

• Χρησιμοποιείται σε πολλές φάσεις της μεταγλώττισης ένας μηχανισμός επεξεργασίας δηλώσεων μέσω του πίνακα συμβόλων

  • Μπορεί ένα όνομα να αναφέρεται σε διάφορες οντότητες του προγράμματος, ανάλογα με το πως χρησιμοποιείται

Υπερφόρτωση

• Σε πολλές γλώσσες προγραμματισμού επιτρέπεται η υπερφόρτωση τελεστών και ονομάτων συναρτήσεων

• Η επαναχρησιμοποίηση του ίδιου συμβόλου δεν προκαλέι σύγχυση, επειδή οι διαφορετικές πράξεις σχετίζονται από μαθηματική άποψη μεταξύ τους

  • Η αποσαφήνιση από τον μεταφραστή της χρήσης ενός συμβόλου, γίνεται εξετάζοντας τους τύπους δεδομένων των τελεστών
• Οι C++, Java, Ada επιτρέπουν εκτεταμένη υπερφόρτωση ονομάτων και τελεστών

• Η Haskell επιτρέπει την υπερφόρτωση των συναρτήσεων, των τελεστών, καθώς και τον ορισμό νέων τελεστών

Υπερφόρτωση Συναρτήσεων

• Υποστηρίζεται από μία λειτουργία αναζήτησης στον πίνακα συμβόλων και όχι μόνο με βάση το όνομα μίας συνάρτησης, αλλά λαμβάνοντας υπόψη και τον αριθμό και τύπο των παραμέτρων

• Αυτή η διαδικασία λέγεται ανάλυση υπερφόρτωσης

• Στην Ada στηρίζεται επίσης και ανάλυση με βάση

  • τον τύπο της επιστρεφόμενης τιμής
  • ονόματα παραμέτρων στον ορισμό της συνάρτησης
• Σε καποιες περιπτώσεις η υπερφόρτωση συνδιάζεται με τους κανόνες αυτόματης μετατρωπής τύπων

Παράδειγμα

Υπερφόρτωση Τελεστών

• Κατά την υπερφόρτωση τελεστών, δεν επηρεάζεται ότι σχετίζεται με την σύνταξή τους (προτεραιότητα και προσεταιριστικότητα)
• Οι τελεστές δε διαφέρουν σημασιολογικά από τις συναρτήσες, αλλά συντακτικά
  • Οι τελεστές συνήθως εκφράζονται με ένθετη μορφή
    πχ. 2+3
  • Οι συναρτήσεις έχουν προθεματική σύνταξη
    πχ. add(2,3)

Παράδειγμα

Υπερφόρτωση Ονόματος για Διαφορετικού Τύπου Οντότητες

• Το ίδιο όνομα μπορεί να χρησιμοποιείται για διαφορετικού είδους οντότητες μέσα στο ίδιο πρόγραμμα
  πχ. μία μεταβλητή, έναν τύπο και μία συνάρτηση
  • Δεν επιτρέπεται στις περισσότερες γλώσσες προγραμματισμού
  • Χρήσιμο αν για κάποιο λόγο πρέπει να περιοριστούν τα ονόματα που επιτρέπεται να χρησιμοποιήσει ο προγραμματιστής

Παράδειγμα

Περιβάλλον

• Το Περιβάλλον διατηρεί τις συνδέσεις ονομάτων με τις ιδιότητες θέσης τους

• Ανάλογα με τη γλώσσα το περιβάλλον εκτέλεσης μπορεί να κατασκευάζεται

  • Στατικά: σε χρόνο φόρτωσης (FORTRAN)
  • Δυναμικά: σε χρόνο εκτέλεσης (LISP)
  • Σε συνδιασμό των δύο (C, C++, Ada, Java)
• Δε συνδέονται θέσεις μνήμης σε όλα τα ονόματα

  • πχ οι σταθερές και οι τύποι που έχουν ονόματα, είναι ονόματα που υπάρχουν μόνο κατά τη μεταγλώττιση
• Η κατασκευή του περιβάλλοντος εκτέλεσης εξαρτάται από τις δηλώσεις

  • μεταγλωττιστής -> αναλύονται για να δημιουργηθεί ο κατάλληλος κώδικας εκχώρησης μνήμης για κάθε περίπτωση
  • διερμηνευτής -> οι συνδέσεις ιδιοτήτων μίας δήλωσης, συμπεριλαμβάνουν και τη σύνδεση ιδιότητας θέσης
• Σε γλώσσες με δομή block

  • Στις καθολικές μεταβλητές μπορεί να εκχωρούνται και θέσεις στατικά (οι ιδιότητές τους δεν μεταβάλλονται κατά την εκτέλεση)
  • Στις τοπικές μεταβλητές εκχωρούνται θέσεις δυναμικά, όταν κατά την εκτέλεση προσεγγίζεται το σχετικό block
  • Η σύνδεση θέσεων σε ονόματα γίνεται με προσέγγιση στοίβας (όπως στον πίνακα συμβόλων)
• Για ένα όνομα σε κάποια στιγμή μπορεί να υπάρχουν πολλες διαφορετικές συνδέσεις θέσης, αλλά μόνο μία είναι προσπελάσιμη

  • αυτό ισχύει για όλες τις γλώσσες με δομή block και λεξική εμβέλεια
• Πρέπει για ένα όνομα να μπορούμε να διακρίνουμε τη δήλωση που έχει προκαλέσει τη σύνδεση συγκεκριμένης θέσης στο όνομα

  • όταν μία θέση έχει εκχωρηθεί ως συνέπεια μίας δήλωσης, λέγεται αντικείμενο
  • στη C οι μεταβλητές σε συναρτήσεις συσχετίζονται με αντικέιμενα, σε αντίθεση με τις καθολικές (δεν συνδέονται με θέση μνήμης)

Παράδειγμα

Χρόνος Ζωής

• Ο Χρόνος Ζωής ενός αντικειμένου αντιπροσωπεύει τη διάρκεια της εκχώρησης από το περιβάλλον

• Οι χρόνοι ζωής των αντικειμένων μπορεί να εκτείνονται έξω από την περιοχή που έιναι δυνατό να προσπελασοτούν

• Αν η γλώσσα προγραμματισμού υποστηρίζει τη χρήση δεικτών, τότε το περιβάλλον εκτέλεσης διαθέτει τη δομή για να παρέχει τις απαραίτητες λειτουργίες

  • Ένας δείκτης είναι αντικείμενο, που η αποθηκευμένη τιμή του έιναι αναφορά, που παραπέμπει σε άλλο αντικείμενο
• Σε γλώσσες με δομή block και δυνατότητα εκχώρησης σε σωρό (heap), έχουμε τρία είδη εκχώρησης θέσεων στο πειρβάλλον εκτέλεσης

  • Στατική (καθολικές μεταβλητές)
  • Αυτόματη (τοπικές μεταβλητές)
  • Δυναμική (εκχώρηση σε σωρό)
• Αυτές οι κατηγορίες λέγονται και κλάσεις αποθήκευσης

• Σε γλώσσες όπως η C επιτρέπεται και η δήλωση κλάσης αποθήκευσης, μαζί με τον τύπο δεδομένων

Μεταβλητές

• Μεταβλητή: είναι ένα αντικείμενο, που η αποθηκευμενη τιμή του αλλάζει κατά την εκτέλεση του προγράμματος
• Κάθε μεταβλητή ορίζεται πλήρως από τις ιδιότητές της, που έιναι το όνομα, η θέση της και ο τύπος της και το μέγεθος του χώρου που καταλμβάνει
  

Εντολές Ανάθεσης με Σημασία Αντιγραφής

• Η τιμή μίας μεταβλητής αλλάζει, με εντολή ανάθεσης x = e, όπου x είναι το όνομα μεταβλητής και e είναι μία έκφραση
  - Η σημασία αυτής της εντολής είναι ότι η e αποτιμάται σε μία τιμή και στη συνέχεια αντιγράφεται στη θέση της x
  - Εάν e είναι όνομα μεταβλητής, (έστω y), τότε η ανάθεση x = y απεικονίζεται ως
  

l-τιμές και r-τιμές

• Καθώς μία μεταβλητή βρίσκεται σε μία θέση και έχει μία αποθηκευμένη τιμή, πρέπει να γίνεται διάκριση μεταξύ αυτών
  • η τιμή που βρίσκεται στη θέση μίας μεταβλητής, αποκαλείται συχνά r-τιμή (εμφανίζεται δεξιά στην εντολή ανάθεσης)
  • η θέση μίας μεταβλητής λέγεται και l-τιμή (εμφανίζεται δεξιά στην εντολή ανάθεσης)
• Η C επιτρέπει την ανάμειξη εκφράσεων με αναθέσεις, όπου μπορεί να έχουμε την r-τιμή και την l-τιμή μίας μεταβλητής
  • πχ x = x + 1;
• Μπορούμε επίσης να ανακτήσουμε τη διεύθυνση μίας μεταβλητής με τη μορφή δείκτη
  • &x είναι ένας δείκτης στη διεύθυνση της x
  • με *&x παίρνουμε πάλι την τιμή της x ως l-τιμή αλλά και r-τιμή
• Αυτά τα χαρακτηριστικά καθιστούν τον προγραμματισμό σε C επιρρεπή σε μη προβλεπόμενες χρήσεις μεταβλητών, που δεν εντοπίζονται εύκολα

Εντολές Ανάθεσης με Σημασία Κοινής Χρήσης

• Σε κάποιες γλώσσες, η εντολή ανάθεσης έχει διαφορετική σημασία: αντί για τις τιμές, αντιγράφονται οι θέσεις
• Αυτή η περίπτωση λέγεται ανάθεση με κοινή χρήση
• Η εντολή x = y προκαλεί τη σύνδεση της θέσης της y στην x
  
• Η Java υποστηρίζει την ανάθεση με κοινή χρήση για όλες τις μεταβλητές αντικειμένων, αλλά όχι για απλά δεδομένα

Σταθερές

• Μία σταθερά είναι μία οντότητα που έχει σταθερή τιμή σε όλη τη διάρκεια ύπαρξής της σε ένα πρόγραμμα
• Διαφέρει από της μεταβλητές, στο ότι η σταθερά δεν έχει συνδεδεμένη ιδιότητα θέσης, αλλά μόνο μία τιμή. Λέμε ότι μία σταθερά έχει σημασία τιμής ατνί για σημασία αποθήκευσης μίας μεταβλητής
  
• Η σταθερά μπορεί να παίρνει τιμή, που γίνεται γνωστή μόνο κατά την εκτέλεση του προγράμματος. Τότε θα πρέπει να αποθηκευτεί η τιμή της στην μνήμη
  • Αντίθετα από μία μεταβλητή, όταν η τιμή μίας σταθεράς υπολογίζεται, δεν μπορεί να μεταβληθεί
• Σε πολλές γλώσσες, και ιδιέταιρα στις συναρτησιακές, δίνεται έμφαση στη χρήση σταθερών αντί για μεταβλητές, λόγω της πολύ απλούστερης σημασίας τους
  • Κάθε όνομα σταθεράς εκφράζει μόνο μία τιμή, που μετά τη δημιουργία της παραμένει αμετάβλητη, ανεξάρτητα από τη θέση ή τη χρήση της στο πρόγραμμα
• Μερικές γλώσσες όπως η Haskell, απαγορεύουν εντελώς τη χρήση μεταβλητών και στηρίζονται αποκλειστικά στη χρήση σταθερών για υπολογισμούς

Στατικές και Δυναμικές Σταθερές

• Οι σταθερές μπορεί να έιναι
  • Στατικές: η τιμή τους μπορεί να υπολογιστεί πριν από την εκτέλεση
    • Χρόνου Μεταγλώττισης
    • Χρόνου Φόρτωσης: υπολογίζονται σε χρόνο φόρτωσης ή στην αρχή εκτέλεσης του προγράμματος
  • Δυναμικές: αυτές που μπορούν να υπολογιστούν μόνο στο χρόνο εκτέλεσης

Ψευδωνυμία

• Όταν ένα αντικείμενο συνδέεται ταυτόχρονα με δύο διαφορετικά ονόματα, λέμε ότι έχουμε ένα ψευδώνυμο
• Η ψευδωνυμία μπορεί να συμβέι με διαάφορους τρόπους, όπως κατά την κλήση διαδικασιών, χρήση μεταβλητών δείκτη, ή όταν γίνεται ανάθεση με κοινή χρήση
• Τα ψευδώνυμα μπορεί να έχουν πιθανώς επιβλαβείς παρενέργειες
  • ως παρενέργεια εντολής ορίζουμε κάποια μεταβολή στην τιμή μίας μεταβλητής, που διατηρείται μετά την εκτέλεσή της
  • δεν είναι όλες οι παρενέργειες επιβλαβείς: η ανάθεση τιμής σε μία μεταβλητή αλλάζει την τιμή της, όπως ρητά επιδιώκεται από τη σημασία της εντολής
  • όμως παρενέργειες, όπως αλλαγές σε μεταβλητές, που δεν αναφέρονται ρητά τα ονόματά τους στην εντολή, είναι πιθανώς επιβλαβείς

Παραδείγματα

Αιωρούμενες Αναφορές

• Αιωρούμενη Αναφορά είναι μία θέση μνήμης, που έχει ανακληθεί η εκχώρησή της από το περιβάλλον, αλλά εξακολουθεί να είναι προσπελάσιμη μέσα από το πρόγραμμα (δηλαδή όταν ένα αντικείμενο είναι προσπελάσιμο πέρα από το χρόνο ζωής του στο περιβάλλον)
• Το πρόβλημα παρουσιάζεται με τη χρήση μεταβλητών δείκτη
• Στη C μπορεί επίσης να έχουμε αιωρούμενες αναφορές λόγω αυτόματης ανάκλησης της εκχώρησης τοπικών μεταβλητών κατά την έξοδο από το block στο οποίο δηλώνονται. Αυτό συμβαίνει λόγω του τελεστή διεύθυνσης "&"

Παραδείγματα

Γραμματικές Χωρίς Συμφραζόμενα

Γραμματική Χωρίς Συμφραζόμενα (Γ.Χ.Σ)

όπου:

• το αλφάβητο, ένα πεπερασμένο σύνολο συμβόλων
• τα τερματικά σύμβολα, ενώ τα μη-τερματικά σύμβολα
• ένα σύνολο κανόνων παραγωγής της μορφής
  • , με
    • μία συμβολοσειρά από σύμβολα
• ένα ένα μη τερματικό σύμβολο που λέγεται αρχή της

Παραγωγή

• Αν η συμβολοσειρά παράγεται από την αρχή μέσω κανόνων της , γράφουμε και -η γλώωσα της

• Σ'αυτή τηνπερίπτωση λέμε ότι η συμμορφώνεται στη σύνταξη των προτάσεων της γλώσσας της
  Παράδειγμα
  

• Αριστερή Παραγωγή: όταν σε κάθε βήμα εφαρμόζουμε κανόνα στο πρώτο μη-τερματικό από τα αριστερά

• Δεξιά Παραγωγή: όταν σε κάθε βήμα εφαρμόζουμε κανόνα στο πρώτο μη-τερματικό από τα δεξιά

Παράγωγα ή Συντακτικά Δέντρα

• Η σύνταξη ενός προγράμματος αποτυπώνεται στο παράγωγο/συντακτικό δέντρο

Παράγωγο/Συντακτικό Δέντρο
Έστω ΓΧΣ

• Για κάθε σύμβολο , το γράφημα με ένα μόνο κόμβο είναι πράγωγο δέντρο, με ρίζα και μοναδικό φύλλο τον
  
• Αν είναι κανόνας του με την κενή συμβολοσειρά, τότε το παρακάτω είναι παράγωγο δέντρο, με ρίζα τον και μοναδικό φύλλο το
  
• Αν τα πρακάτω είναι παράγωγα δέντρα με ρίζες τα και παραγώμενες συμβολοσειρές τις
  
  και αν είναι κανόνας του , τότε το παρακάτω είναι παράγωγο δέντρο με ρίζα και παραγόμενη συμβολοσειρά την
  

Παράδειγμα

Αφαιρετικά Συντακτικά Δέντρα

• Τα παράγωγα δέντρα διατηρούν όλη την πληροφορία σχετικά με την παραγωγή μίας συμβολοσειράς από μία γραμματική
• Μέρος αυτής της πληροφορίας δεν επηρεάζει τη σημασία της γλώσσας προγραμματισμού και μπορεί να παραληφθεί για την απλούστευση του δέντρου
• Το Αφαιρετικό συντακτικό δέντρο δεν περιλαμβάνει όλες τις πληροφορίες

Παράδειγμα

Διφορούμενες ή Ασαφείς Γραμματικές

• Μία ΓΧΣ λέγεται διφορούμενη ή ασαφής όταν υπάρχει πρόταση της γλώσσας με τουλάχιστον δύο παράγωγα δέντρα (δύο διαφορετικές αριστερές ή δεξιές παραγωγές)
• Η ΓΧΣ που περιγράφει τη σύνταξη μίας γλώσσας δεν πρέπει να είναι διφορούμενη, ή αν είναι, το πρόβλημα πρέπει να αντιμετοπίζεται κατά τη μεταγλώττιση

Ασάφεια Προτεραιότητας Τελεστών

Παράδειγμα

• Για να διορθώσουμε το πρόβλημα ασάφειας προτεραιότητας τελεστών:
  • Ομαδοποιούμε τους τελεστές με την ίδια προτεραιότητα σε κανόνα με κοινό μη-τερματικό σύμβολο

Ασάφεια Πορσεταιριστικότητας Τελεστών

Παράδειγμα

• Για να διορθώσουμε το πρόβλημα ασάφειας προσεταιριστικότητας τελεστών:
  • Ένας κανόνας ΓΧΣ παράγει δέντρο με αριστερή προσεταιριστικότητα αν αυτός είναι αποκλειστικά αριστερά αναδρομικός

Ασάφεια Μετέωρου Else

Παράδειγμα

Συμβολισμός BNF/EBNF

• BNF (Backus Normal Form)
  • Τα μη-τερματικά σύμβολα περικλείονται από και
  • Για κανόνες παραγωγής χρησιμοποιείται το ή κάποιες φορές το
  • Οι κανόνες παραγωγής για το ίδιο μη-τερματικό αναφέρονται σε έναν ενιαίο κανόνα
• EBNF (Extended BNF)

Παράδειγμα

Συντακτικά Διαγράμματα

• Συντακτικό Διάγραμμα: μία γραφική παράσταση κανόνων EBNF
  • τετράγωνα: μη-τερματικά
  • κύκλοι: τερματικά
  • τόξα: δομές ακολουθίας ή επιλογής
  • αριστερό μέρος: μη-τερματικό του οποίου ο κανόνας αναπαριστάται

Παραδείγματα

Κανονικές Εκφράσεις

Κανονικές Εκφράσεις (Ορισμός)

• Δοθέντος πεπερασμένου αλφαβήτου , Κανονικές Εκφράσεις είναι οι σταθερές

  • : το κενό σύνολο
  • : το σύνολο με την κενή συμβολοσειρά
  • : το σύνολο με τη συμβολοσειρά , όπου
• Δοθέντων των Κανονικών Εκφράσεων και , ορίζουμε επίσης τις ακόλουθες πράξεις ως Κ.Ε.

  • : η Παράθεση της με την
  • : η Διάζευξη της με την
  • : η Kleene Star της , το ελάχιστο υπερσύνολο της που περιλαμβάνει την και είναι κλειστό προς την παράθεση
• Η Kleene Star εκφράζει το σύνολο όλων των συμβολοσειρών που σχηματίζονται με παράθεση πεπερασμένου αριθμού (ή μηδέν) συμβολοσειρών της

  • πχ
• Προτεραιότητα Τελεστών: υποθέτουμε πως η προτεραιότητα πράξεων πάει ως εξής:

  1. Kleene Star
  2. Παράθεση
  3. Διάζευξη

Κ.Ε. -> Ελάχιστο ΝΠΑ

Κ.Ε. -> Συντακτικό Δέντρο

• Απλό
  Παράδειγμα
  

Συντακτικό Δέντρο -> ΜΝΠΑ

• Ανάπτυξη Thompson
  • ΜΝΠΑ Κενής Συμβολοσειράς
    
  • ΜΝΠΑ Χαρακτήρα - Πρότυπο
    
  • ΜΝΠΑ Παράθεσης
    
  • ΜΝΠΑ Διάζευξης
    
  • ΜΝΠΑ Kleene Star
    
• Συνδιάζοντας τα παραπάνω ΜΝΠΑ χτίζουμε το τελικό ΜΝΠΑ από το φύλλα πρός τη ρίζα του Συντακτικού Δέντρου
  Παράδειγμα
  

ΜΝΠΑ -> ΝΠΑ

• Βρίσκουμε την ε-Κλειστότητα κάθε κατάστασης του ΜΝΠΑ
  - ε-Κλειστότητα της : το σύνολο όλων των καταστάσεων που μπορούν να προσεγγιστούν αποκλειστικά με ε-μεταβάσεις από την
  Παράδειγμα
  
• Το νέο σύνολο καταστάσεων είναι η ε-κλειστότητα κάθε κατάστασης του αρχικού Αυτόματου, δηλαδή σύνολο από καταστάσεις
• Η νέα Συνάρτηση Μετάβασης ορίζεται ως
  • Για κάθε σύνολο από καταστάσεις , η μετάβαση του μέσω κάποιου συμβόλου , οδηγεί στην ένωση, από τις ε-κλειστότητες, των καταστάσεων στις οποίες οδηγούμασταν, από τις καταστάσεις του
• Η Αρχή του ΝΠΑ είναι η ε-κλειστότητα της αρχής του ΜΝΠΑ
• Οι τελικές καταστάσεις του ΝΠΑ είναι όλες οι καταστάσεις που περιέχουν τελικές καταστάσεις του ΜΝΠΑ

Παράδειγμα

ΝΠΑ -> Ελάχιστο ΝΠΑ

• Χωρίζουμε τις καταστάσεις σε δύο κλασεις , όπου
  • οι μη-τελικές καταστάσεις του ΝΠΑ
  • οι τελικές καταστάσεις του ΝΠΑ
• Αναδρομικά ελέγχουμε αν σε κάθε κλάση, όλες οι μεταβάσεις, οδηγούν στην ίδια κλαση
  • δλδ αν ή η είναι εντάξει
• Αν ένα υποσύνο μίας κλάσεις έχει διαφορετικά αποτελέσματα, δημιουργούμε νέα κλαση και επαναλαμβάνουμε τη διαδικασία, μέχρι κάθε κλαση να χαρακτηρίζεται από όμοιες μεταβάσεις σε άλλες κλάσεις
• Το Ελαχιστοποιημένο ΝΠΑ έχει μία κατάσταση για κάθε κλαση του ΝΠΑ, και η μετάβαση από κάθε κατάσταση είναι προφανής
  Παράδειγμα
  

Γεννήτρια Λεξικού Αναλυτή

• Η Γεννήτρια Λεξικού Αναλυτή είναι ένα πρόγραμμα που δέχεται ως είσοδο ένα σύνολο από ορισμούς αναγνωριστικών σε μορφή Κανονικών Εκφράσεων και παράγει ως έξοδο έναν λεξικό αναλυτή
• Ένα πρόγραμμα λεξικού αναλυτή πρέπει να μπορεί να
  • Διακρίνει διάφορους τύπους αναγνωρηστικών (πχ αριθμούς, μεταβλητές, λέξεις κλειδιά, κλπ...)
  • Αποκόπτει τη σευμβολοσειρά εισόδου σε πολλά μέρη, που το καθένα ανήκει σε μία από τις γλώσσες των Κανονικών Εκφράσεων
  • Αποφασίζει με ποιό τρόπο θα προχωρήσει αν υπάρχουν πολλοί διαφορετικοί τρόποι αποκοπής της εισόδου σε επιμέρους συμβολοσειρές

Τρόπος Λειτουργείας

• Απλή Προσέγγιση
  • Σύνθεση ενός ΝΠΑ για κάθε ορισμό αναγνωρηστικού και προσωμοίωσή, με τη σειρά, ένα προς ένα
  • Αρκετά αργή λύση. Προτιμάται η σύνθεση ενός μόνο ΝΠΑ από το σύνολο ορισμών, που προσομοιώνει ταυτόχρονα όλους τους ορισμούς αναγνωρηστικών
• "Πραγματική" Προσέγγιση
  1. Δημιουργεία ΜΝΠΑ για κάθε ΚΕ αναγνωρηστικού
  2. Επισημείωση των καταλήξεων κάθε ΜΝΠΑ με το όνομα του αναγνωρηστικού που δέχονται
  3. Συνδιασμός των ΜΝΠΑ σε ένα ενιαίο ΜΝΠΑ, με την προσθήκη μίας νέας αρχικής κατάστασταση και ε-μεταβάσεις στην αρχή κάθε επιμέρους ΜΝΠΑ
  4. Μετατροπή του ενιαίου ΜΝΠΑ σε ΝΠΑ
  5. Κάθε κατάληξη του ΝΠΑ θα αποτελείται από ένα σύνολο καταστάσεων του ΜΝΠΑ με τουλάχιστον μία κατάληξη από αυτές του βήματος 2. Η επισήμανση χρησιμοποιείται για την αναγνώρηση του τύπου του αναγνωρηστικού
• Συγκρούσεις
  • Από τη διαδικασία μετατροπής ΜΝΠΑ σε ΝΠΑ, μία κατάληξη του ΝΠΑ μπορεί να αντιστοιχεί σε πολλαπλές επισημανσμένες καταλήξεις του ΜΝΠΑ. Στην περίπτωση που ο τύπος ενός αναγνωρηστικού είναι αμφίβολος, μπορούμε
    • Ο λεξικός αναλυτής να παράγει λάθος, ενώ προσπαθούμε οι ορισμοί να είναι αμοιβαίως αποκλειώμενοι, δλδ αν μην υπάρχουν συμβολοσειρές που αναγνωρίζονται με πάων από έναν τύπο
    • Ο χρήστης της γενήτριας να επιλέγει ποιό από τα αναγνωρηστικά προτιμάται
      • Συνήθως η επικάλυψη αντιμετοπίζεται συμερίζοντας την σειρά εμφάνισης των αναγνωρηστικών στην είσοδο της γεννήτριας Λ.Α.

Παράδειγμα

Flex

Κανονικές Εκφράσεις

Σύνταξη

Παράδειγμα

• Αν κάποια συμβολοσειρά ταυτίζεται με περισσότερους από έναν ορισμούς, , η Flex την ταυτίζει με τον νωρίτερα ορισμένο ορισμό
• Αν κάποια συμβολοσειρά παράγεται από μία Κ.Ε. και ταυτόχρονα είναι μέρος μεγαλύτερης λεξικής μονάδας, τότε η Flex την αναγνωρίζει ως μέρος της μεγαλύτερης λεξικής μονάδας

Συντακτική Ανάλυση

Η Συντακτική Ανάλυση - Σ.Α. δέχεται αναγωνριστικά που συγκροτούν το πηγαίο πρόγραμμα, του οποίου τη συντακτική δομή θα αναγνωρίσει/καταγράψει

• Αν το πρόγραμμα συμμοφρώνεται στον ορισμό σύνταξης της Γλ.Πρ., τότε η ΣΑ μπορεί να καταγράφει τη δομή του σε μορφή συντακτικού δέντρου, την ενδιάμεση αναπαράσταση (υπάρχουν και γραμμικές ενδιάμεσες αναπαραστάσεις)
• Αν το πρόγραμμα δεν συμμορφώνεται στον ορισμό σύνταξης της Γλ.Πρ., τότε ο αλγόριθμος ΣΑ, εντοπίζει ένα συντακτικό λάθος, και μετά εκτελεί μία διαδικασία ανάκαμψης, ώστε να συνεχίσει η ΣΑ μέχρι το τέλος του Προγράμματος
• Η ΣΑ κατά τη λειτουργεία της ενεργοποιεί τους ελέγχους που σχετίζονται με τη σημασία του προγράμματος - αντλούνται πληροφορίες από το συντακτικό δέντρο και τον πίνακα συμβόλων
• Το συντακτικό δέντρο αντικατοπτρίζει τη σειρά ανίχνευσης των αναγνωρισιτικών στη δομή του προγράμματος
• Μετάφραση σε ένα πέρασμα: όταν μία μόνο διάσχιση του δέντρου αρκεί για την εκτέλεση σημασιολογικών ελέγχων και δεν αποθηκεύεται κάποια δομή δεδομένων στη μνήμη
• Μετάφραση σε πολλά περάσματα: για πιο απαιτητικούς σημασιολογικούς ελέγχους, που αποθηκεύεται η δομή του συντακτικού δέντρου

Ανάκαμψη από Λάθη

• Οι τεχνικές ανάκαμψης, που μπορούν να εφαρμοστούν, εξαρτώνται από τη μέθοδο ανάλυσης
• Γενικές αρχές
  • Ο εντοπισμός λάθους είναι αποτελεσματικός, όταν γίνεται έγκαιρα. Προτιμώνται αλγόριθμοι με μηχανισμούς πρόβλεψης του κανόνα που θα εφαρμοστεί
  • Ο μεταγλωττιστής θα πρέπει να εντοπίζει πραγματικά λάθη και όχι υποτιθέμενα λάθη εξαιτίας της διαδικασίας ανάκαμψης από το προηγούμενο λάθος (διαδιδόμενα λάθη)
  • Μετά το εντοπισμό λάθους πρέπει να επιλέγεται σημείο συνέχισης της ανάλυσης, δηλαδή εκεί που ξαναενεργοποιείται η δυνατότητα εντοπισμού λαθών
  • Θα πρέπει να αποκλείεται η πιθανότητα μετάπτωσης του αναλυτή σε αέναους βρόγχους επανάληψης, που δεν επιτρέπουν τη συνέχιση της ανάγνωσης του πηγαίου προγράμματος

Στρατηγικές Ανάκαμψης από Λάθη

• Διακρίνουμ 4 βασικές στρατηγικές ανάκαμψης
  1. Ανάκαμψη σε κατάσταση "Πανικού"
     Μετά από τον εντοπισμό λάθους "αγνωούνται" λεξικές μονάδες, μέχρι να βρεθεί μία από την οποία μπορεί να συνεχίσει με ασφάλεια την ανάλυση (μονάδες συγχρονισμού πχ. επιλεγμένοι διαχωριστές)
     Πλεονεκτίματα: απουσία αέναων βρόγχων και διαδιδόμενων λαθών, για όσο αγνούνται λεξικές μονάδες μετά τον εντοπισμό λάθους
  2. Ανάκαμψη σε επίπεδο φράσης
     Μπορεί να αντικαθίσταται, μετά από λάθος, ένα πρόθεμα της εναπομείνασας εισόδου, ώστε να μπορεί να συνεχίσει την ανάλυση
     πχ. Αντικατάσταση κόμματος με ερωτηματικό, εισαγωγή ερωτηματικού εκεί που πρέπει να υπάρχει
     Χρειάζεται προσοχή στην επιλογή των επιτρεπτών διορθώσεων, ώστε να αποφεύγονται οι αέναοι βρόγχοι. Δεν είναι πάντα εύκολη η εφαρμογή της
  3. Κανόνες παραγωγής για λάθη:
     Αν υπάρχει δυνατότητα πρόβλεψης των λαθών, μπορούν να διατυπωθούν επιπλέον κανόνες παραγωγής, που καθοδηγούν την ανάλυση, όταν αναγνωρίζονται αυτά τα λάθη
     Κάθε φορά που χρησιμοποιείται από τον αναλυτή ένας τέτοιος κανόνας, παράγεται και κατάλληλο διαγνωστικό μήνυμα
  4. Συνολική Διόρθωση
     Η υλοποίησή της εππιτυγχάνεται με την εφαρμογή κατάλληλου αλγορίθμου διόρθωσης λαθών, με όσο το δυνατόν μικρότερο αριμθμό αλλαγών. Αυτοί οι αλγόριθμοι έχουν αποδειχθεί πολύ δαπανηροί στην πράξη, και είναι περισσότερο θεωρητικού, παρά πρακτικού ενδιαφέροντος

Ορισμός Σύνταξης Γλώσσας Προγραμματισμού

• Για τον ορισμό της συντακτικής δομής των γλωσσών προγραμματισμού, χρησιμοποιούνται Γραμματικές Χωρίς Συμφρζόμενα
  - Τερματικά σύμβολα είναι τα αναγνωρηστικά (γράφονται με bold)
  - Μη τερματικά σύμβολα εκφράζουν τις συντακτικές δομές της γλώσσας (assig-stmt, expr, term...) (γράφονται με italics)
  - Η Αρχή της ΓΧΣ αντιστοιχεί σε ένα οποιοδήποτε πρόγραμμα (σλυμβολο στο αριστερό μέρος του πρώτου κανόνα)
  Παράδειγμα
  

Κατηγοριοποίηση Γραμματικών

Το σύνολο FIRST

• Αν είναι συμβολοσειρά που αποτελείται από μη-τερματικά ή/και τερματικά σύμβολα μίας γραμματικής, τότε το σύνολο των (τερματικών συμβόλων ή ) που μπορεί να εμφανίζονται στην αρχή όλων των συμβολοσειρών, που παράγονται από τη μέσω κανόνων

Αλγόριθμος Υπολογισμού FIRST

• Είσοδος: Γραμματική και μία προτασιακή μορφή
• Έξοδος: το σύνολο
  
• Αν το είναι τερματικό ή , το
• Αν το είναι μη-τερματικό, το είναι η ένωση των όλων των συμβολοσειρών που μπορούν να παραχθούν με έναν κανόνα από το
• Αν το είναι σύζευξη από τερματικά ή/και μη τερματικά
  • Παίρνουμε με τη σειρά κάθε επιμέρους σύμβολο και προσθέτουμε στο , το
  • Μέχρι να βρούμε που να μην παράγει το , ή να τελειώσουν τα σύμβολα
  • Αν η παράγει το , το προσθέτουμε στη

Το Σύνολο FOLLOW

• Αν ένα μη-τερματικό σύμβολο, τότε το σύνολο των τερματικών συμβόλων που μπορεί να εμφανιστούν αμέσως μετά από αυτό, σε όλες τις περιπτώσεις παραγώμενων συμβολοσειρών

Αλγόριθμος Υπολογισμού

• Είσοδος: Γραμματική και ένα μη-τερματικό
• Έξοδος: το σύνολο
  
• Αν είναι η αρχή της γραμματικής, τότε βάζουμε το στο
• Για κάθε κανόνα της γραμματικής, μορφής (με το στο δεξί του μέρος)
  • αν το αρχίζει με τερματικό, βάλε αυτό το τερματικό στο
  • αν το αρχίζει με μη-τερματικό, βάλε το στο
  • αν το έιναι ή παράγει , βάλε το στο

Παράδειγμα

Γραμματικές LL(1)

• Μία γραμματική είναι αν-ν
  1. Για κάθε κανόνα ισχύει για όλα τα με
  2. Για κάθε μη-τερματικό , τέτοιο ώστε ισχύει

Απομάκρυνση Αριστερής Αναδρομικότητας

Άμεση Αριστερή Αναδρομικότητα

• Πρόβλημα με κανόνα παραγωγής του τύπου

  • : συμβολοσειρές από τερματικά ή/και μη-τερματικά
  • : συμβολοσειρές από τερματικά ή/και μη-τερματικά που δεν ξεκινούν από
• Η λύση δίνεται με την μετατροπή της αριστερής αναδρομής σε δεξιά ως εξής:

  • όπου ένα νέο μη-τερματικό σύμβολο
• Η παραπάνω αντικατάσταση δεν επηρεάζει τη γλώσσα της γραμματικής

Έμμεση Αριστερή Αναδρομικότητα

• Πρόβλημα με κανόνες παραγωγής του τύπου
• Για να εφαρμοστεί ο αναγκαίος μετασχηματισμός, προϋποθέτει η γραμματική
  - Να μην περιέχει κυκλικούς κανόνες παραγωγής
  - πχ , ,
  - Να μην περιέχει κανόνες-ε
  - Σύμφωνα με θεώρημα, όταν στη γραμματική υπάρχουν κανόνες-ε, είναι γενικά δυνατή η απομάκρυνσή τους με διατύπωση ισοδύναμης γραμματικής
  
• Πάρε ΜΕ ΤΗ ΣΕΙΡΑ τα μη-τερματικά και
  • Έλεγξε αν έχουν κανόνες, που το δεξί τους μέρος, ξεκινά με μη-τερματικό, που έχει ήδη ελεγχθεί
  • Αντικατέστησε κάθε κανόνα της μορφής με τους κανόνες για κάθε κανόνα (του προηγούμενου μη-τερματικού) της μορφής
  • Απομάκρυνε την άμεση αριστερή αναδρομή για τους κανόνες του

Παράδειγμα

Μετασχηματισμός Γραμματικής σε LL(1) - Αριστερή Παραγοντοποίηση

• Υπάρχουν γραμματικές που εμφανίζουν σε έναν τουλάχιστον κανόνα της γραμματικής, δύο ή περισσότερες εναλλακτικές με το ίδιο πρόθεμα. Για να εκτελέσουμε προβλέπουσα ανάλυση, αυτοί οι κανόνες πρέπει να εξαλειφθούν
• Αριστερή Παραγοντοποίηση Παράδειγμα
  • Η
    • 'if' 'then'
      'if' 'then' 'else'
      'άλλο'
  • Γίνεται
    • 'if' 'then'
      'άλλο'
    • 'else'
      
• δλδ Βρίσκουμε τα δεξιά μέρη με το κοινό πρόθεμα και τα αποσπούμε, αφήνοντας μόνο το κοινό πρόθεμα στον αρχικό κανόνα, και δημιουργόντας νέο μη-τερματικό για κάθε διαφορετικό επίθεμα, το οποίο μπορεί να γίνει είτε το επίθεμα, είτε

Γραμματικές LR(1)

Για να είναι μία γραμματική πρέπει:

1. Αν υπάρχει στοιχείο της μορφής στο σύνολο για κάποιο τερματικό , τότε δεν θα υπάρχει στο ίδιο σύνολο το συμπληρωμένο στοιχείο (shift-reduce conflict)
2. Ένα σύνολο στοιχείων δεν μπορεί να περιέχει πανω από ένα συμπληρωμένα στοιχεία της μορφής και (reduce-reduce conflict)

Γραμματικές SLR(1)

• Οι γραμματικές είναι και (κανονική) - , αλλά η ανάλυση μπορεί να έχει περισσότερες καταστάσεις από την
• Οι γραμματικές δεν είναι απαραίτητα και

Αλγόριθμοι Συντακτικής Ανάλυσης

• Καθοδική Συντακτική Ανάλυση
  • Ρίζα (αρχή γραμματικής) προς φύλλα (αναγνωρισιτικά τερματικών)
  • Προϋποθέτει μη-αριστερά αναδρομική γραμματική
  • Αντιστοιχεί σε αριστερές παραγωγές της γραμματικής
• Ανοδική Συντακτική Ανάλυση
  • Φύλλα (αναγνωριστικά τερματικών) προς φύλλα (αρχή γραμματικής)
  • Εφαρμόζεται σε ευρύτερη οικογένεια γραμματικών
  • Αντιστοιχεί σε δεξιές παραγωγές της γραμματικής
• Αλγόριθμοι Οπισθοδρόμησης
  • Επιλεγεται εξ αρχής σειρά εφάρμοσης κανόνων γραμματικής και αν η ανάλυση φτάσει σε σημείο που δεν μπορεί να προχωρήσει
    • Αναιρείται ένας ή περισσότεροι κανόνες και εφαρμόζονται διαφορετικοί για τα ίδια σύμβολα
  • Υψηλό υπολογιστικό κόστος
  • Καθυστερημένη ανίχνευση λαθών
  • DFS εφαρμογή κανόνων γραμματικής
• Αλγόριθμοι Πρόγνωσης
  • Διαβάζονται ένα ή περισσότερα τερματικά σύμβολα και
    • με βάση αυτά αποφασίζεται ποιοός κανόνας θα χρησιμοποιηθεί, από αυτούς που αναφέρονται σε ένα συγκεκριμένο μη-τερματικό
  • Συγκριτικά αποδοτικότερη μεταγλώττιση και πιο απλή ανάκαμψη από λάθη

Ονοματολογία Αλγορίθμων Συντακτικής Ανάλυσης

Ένας αλγόριθμος ΣΑ παίρνει όνομα της μορφής

• Όπου
  • αναφέρεται στη φορά ανάγνωσης των συμβόλων,που αντιστοιχούν στα αναγνωριστικά συμβολοσειρών του πηγαίου προγράμματος
    • δηλώνει πως η είσοδος αναγνωριστικών στον αλγόριθμο γίνεται από τα αριστερά προς τα δεξιά
  • αναφέρεται στον τύπο παραγωών που ακολουθεί ο αλγόριθμος
    • δηλώνει αριστερές παραγωγές (χαρακτηριστικό της καθοδικής ανάλυσης)
    • δηλώνει δεξιές παραγωγές (χαρακτηριστικό της ανοδικής ανάλυσης)
  • αναφέρεται στον αριθμό τερματικών συμβόλων που διαβάζονται για να αποφασιστεί ο κανόνας της γραμματικής που θα χρησιμοποιηθεί

Καθοδική ΣΑ

Καθοδική ΣΑ με Οπισθοδρόμηση

1. Για ένα τερματικό σύμβολο, εφαρμόζεται ο πρώτος κανόνας που αναφέρεται σε αυτο
2. Στη συμβολοσειρά που προκύπτει επιλέγεται το πρώτο από τα αριστερά μη τερματικό και εφαρμόζεται ο πρώτος κανόνας που αναφέρεται σε αυτό
3. Επαναλαμβάνουμε το βήμα 2, για κάθε μη τερματικό σύμβολο που ακολουθεί μέχρι να παραχθεί
   • μία σειρά που αντιστοιχεί στη συμβολοσειρά εισόδου
   • μία σειρά τερματικών που διαφέρει από το αντίστοιχο τμήμα της εισόδου
     Όταν συμβεί αυτό αναιρείται ο τελευταίος κανόνας που εφαρμόστηκε και επιλέγεται ο επόμενος για το αντίστοιχο μη τερματικό
     Αν εξαντληθούν οι κανόνες για το συγκεκριμένο μη τερματικό, αναιρείται ο επόμενος πιο πρόσφατος κανόνας
     Οι αναιρέσεις συνεχίζουν μέχρι να μπορεί να συνεχίσει η ανάλυση, ή να επιστρέψουμε στην αρχή της γραμματικής, που σημαίνει πως βρέθηκε συντακτικό λάθος

• Στην ουσία είναι DFS αναζήτηση για τη σωστή παραγωγή μίας συμβολοσειράς

Παράδειγμα

• Εξαιρετικά αργός
• Ανίχνευση λάθους όταν έχει δοκιμαστεί κάθε πιθανή παραγωγή
• Τα περισσότερα (αν όχι όλα) χαρακτηριστικά που μπορεί να είναι απιθυμητά σε μία γλώσσα προγραμματισμού, μπορούν να περιγραφούν απο γραμματικές με απαιτήσεις περιορισμένης ή ανύπαρκτης οπισθοδρόμησης

Καθοδική ΣΑ Προβλεπουσας Αναδρομικής Κατάβασης

• Κάθε κανόνας της γραμματικής, για ένα μη τερματικό σύμβολο, εκφράζεται από μία διαδικασία (function)
  • Το αριστερό μέρος είναι το όνομα, το δεξί καθορίζει τον κώδικα
• Μία σειρά συμβόλων εκφράζεται από την κατά σειρά κλήση των αντίστοιχων συναρτήσεων
• Η ΣΑ προβλέπουσας αναδρομικής κατάβασης αποτελείται από
  • Μία καθολική μεταβλητή, με την τιμή του αναγνωριστικού που διαβάστηκε πιο πρόσφατα
  • Μία διαδικασία που ελέγχει αν το τρέχον αναγνωριστικό είναι ίδιο με κάποιο αναμενόμενο, και αν είναι καλεί τη διαδικασία ανάγνωσης του επόμενου αναγνωριστικού, που ενημερώνει την καθολική μεταβλητή
  • Τις διαδικασίες ανάλυσης για μη τερματικά σύμβολα της γραμματικής
  • Την κύρια συνάρτηση, που διαβάζει το πρώτο αναγνωριστικό, και έπειτα καλεί τη διαδικασία ανάλυσης για το μη τερματικό της αρχής της γραμματικής

Παράδειγμα
Έστω η ΓΧΣ:

'+'
'-'


'*'
'\'

'('')'
'αριθμός'
Αυτό μεταφράζεται σε κώδικα

// Ena gia kathe typo anagnwristikou
typedef  enum {PLUS,MINUS,MULT,DIV,LPAR,RPAR,NUMBER,END_FILE} TokenType;
// H katholiki metavlhth epomenou anagnoristikou
TokenType token;

void error() {
	printf("Syntax Error \n");
	exit(0);
}
//Synarthsh elegxou
void match(TokenType expexted_token) {
	if (token == expected_token)
		token = getToken(); //Lexikos analyths
	else
		error();
}

//Synarthseis analyshs mh termatikwn
void E();

void F() { // F ->
	switch(token){
		case LPAR:  //'('E')' 
			token = getToken();
			E();
			match(RPAR);
			break;
		case NUMBER: // 'arithmos'
			token = getToken();
			break;
		default:
			error();
	}
}

void Fr() { //Fr ->
	switch(token){
		case MULT: // '*'FFr
			token = getToken();
			F();
			Fr();
			break;	
		case DIV: // '/'FFr
			token = getToken();
			F();
			Fr();
			break;
		default: // ε
			return;
	}
}

void T() { //T -> FFr
	F();
	Fr();
}

void Tr() { //Tr ->
	switch(token) {
		case PLUS: //'+'TTr
			token = getToken();
			T();
			Tr();
		case MINUS: //'-'TTr
			token = getToken();
			T();
			Tr();
		default: // ε
			return;
	
	}
}

void E() { //E -> TTr
	T();
	Tr();
}

void main() {
	token = getToken();
	E();
	if (Token != END_FILE)
		return error();
}

Copy

• Όπως όλοι οι αλγόριθμοι καθοδικής ανάλυσης, δεν εφαρμόζεται σε αριστερά αναδρομικές γραμματικές

  • χρειάζεται μετασχηματισμός της γραμματικής σε μη-αριστερά αναδρομική
• Η προβλεπουσα αναδρομική κατάβαση πρέπει να επιλέγει σε κάθε βήμα τον σωστό κανόνα μεταξύ των πιθανών επριπτώσεων (έτσι ώστε να αποφέυγεται η οπισθοδρόμηση)

  • η επιλογή του κανόνα γίνεται με βάση το τερματικό σύμβολο που βρίσκεται σε κάθε θέση
• Απαραίτητη προϋπόθεση για να εφαρμοστεί, είναι η γραμματική να είναι

• Αν δεν είναι τότε πρέπει να μετασχηματιστέι σε

• Η γενική μορφή μιας συνάρτησης ανάλυσης είναι η εξής
  

• Σε γενικούς όρους δουλεύει ως εξής

  • Όταν εκτελείται η διαδικασία , για ένα μη-τερματικό , ελέγχεται αν το τρέχον αναγνωριστικό εμφανίζεται σε ένα για το δεξί μέρος κάποιου κανόνα του
  • Αν εμφανίζεται, τότε εφαρμόζεται αυτός ο κανόνας
  • Διαφορετικά υπάρχει συντακτικό λάθος, εκτός και αν περιέχεται παραλέιψιμη συμβολοσειρά στο δεξί μέρος του , οπότε ελέγχεται αν το αναγνωριστικό βρίσκεται στο
• Στην προβλέπουσα αναδρομική κατάβαση, τα συντακτικά λάθη εντοπίζονται άμεσα, και αυτό διευκολύνει την ανάκαμψη, που είναι πιο κατάλληλη για κάθε περίπτωση

  • Όμως η απαίτηση να μην είναι αριστερά αναδρομική η γραμματική, αποκλειει την επιθυμητή ιδιότητα της αριστερής προσεταιριστικότητας
  • Το πρόβλημα αντιμετωπίζεται με προσεκτική σχεδίαση της αλληλεπίδρασης συναρτήσεων, που αντιστοιχούν στα μη τερματικά σύμβολα της γραμματικής

Καθοδική ΣΑ Προβλεπουσας Αναδρομικής Κατάβασης με Ανάκαμψη σε Κατάσταση "Πανικού"

• Μετά από εντοπισμό λάθους, "αγνοούνται" λεξικές μονάδες μέχρι να βρεθεί μία από την οποία μπορεί να συνεχίσει με ασφάλεια η ανάλυση (λεξικές μονάδες συγχρονισμού)
• Πρέπει να επιλεγούν οι κατάλληλες λεξικές μονάδες συγχρονισμού για κάθε πιθανή κατάσταση από την οποία μπορεί να περάσει η ανάλυση
  • Υποψήφιες είναι οι λεξικές μονάδες του συνόλου του μη-τερματικού, στο δεξί μέρος ενός κανόνα παραγωγής
• Ιδιέταιρα χρήσιμα είναι και τα σύνολα , που λαμβάνονται υπόψη για να αποτρέπεται η προσπέραση λεξικών μονάδων με καίρια σημασία, εξαιτίας πιθανής απουσίας του τερματικού συμβόλου που αναμένεται (όπως το άνοιγμα μίας έφρασης, όταν λείπει το ";")

Παράδειγμα

Ανάλυση LL(1)

• Στην ανάλυση , για κάθε συνδιασμό μη-τερματικού συμβόλου και τερματικού συμβόλου , ο αλγόριθμος αποφασίζει την ενέργεια που θα εφαρμώσει, με βάση έναν πίνακα

• Ο πίνακας υπολογίζεται εφαρμόζοντας έναν αλγόριθμο στους κανόνες της γραμματικής

• Το μη τερματικό σύμβολο της επόμενης παραγωγής, δίνεται κάθε φορά από την κορυφή της στοίβας που συντηρείται από τον αλγόριθμο ανάλυσης

• Λειτουργεί ως εξής

  • Η στοίβα αρχικοποιείται με το σύμβολο και ακολουθείται από το σύμβολο αρχής της γραμματικής
    • Αν στην κορυφή της στοίβας έχουμε τερματικό και είναι ίδιο με αυτό στην κεφαλή ανάγνωσης (τρέχον αναγνωριστικό), αφαιρείται από τη στοίβα και διαβάζεται το επόμενο αναγνωριστικό. Αν τα δύο αναγνωριστικά δεν ταυτίζονται, τότε έχουμε λάθος
    • Αν στην κορυφή της στοίβας έχουμε μη-τερματικό, επιλέγεται από τον πίνακα ανάλυσης , το δεξί μέρος του κανόνα που αντιστοιχεί στο μη-τερματικό και στο τερματικό που υποδεικνύει η κεφαλή ανάγωνσης
      Αν η θέση του πίνακα έχει τιμή error (κενή θέση), τότε έχουμε λάθος. Διαφορετικά αντικαθίσταται το μη τερματικό της κορυφής της στοίβας με τα σύμβολα του δεξιού μέρους του κανόνα που επιλέχθηκε
    • Η ανάλυση ολοκληρώνεται με επιτυχία, όταν προσεγγιστεί το τέλος της συμβολοσειράς εισόδου, και η στοίβα περιέχει μόνο το

Παράδειγμα

Αλγόριθμος Υπολογισμού Πίνακα Ανάλυσης

• Για κάθε κανόνα της γραμματικής
  • για κάθε τερματικό
    • προσθεσε τον κανόνα στη θέση
      • αν , βάλε τον κανόνα στη θέση , για κάθε τερματικό
        • αν , βάλε τον κανόνα στη θέση
• Στις θέσεις που μένουν κενές εννοείεται πως γράφουν
  Παράδειγμα
  
  
  

Ανάλυση LL(1) με Ανάκαμψη σε Κατάσταση "Πανικού"

• Στην εντοπίζεται λάθος όταν στην κορυφή της στοίβας έχουμε ένα μη-τερματικό , τέτοιο ώστε το τρέχον σύμβολο εισόδου να μην ανήκει στο και αν σε αυτό συμβαίνει να περιέχεται το , ούτε στο σύνολο (κενές θέσεις του πίνακα)
• Η ανάκαμψη σε κατάσταση "πανικού" υλοποιείται προσδιορίζοντας την κατάλληλη ενέργεια για κάθε περίπτωση κενής θέσης στον πίνακα ανάλυσης
  • pop: Αφαίρεση του από τη στοίβα
  • scan: προσπέρασμα συμβόλων στην είσοδο μέχρι τον εντοπισμό λεξικής μονάδας που μπορεί να χρησιμοποιηθεί για την επανεκκινηση της ανάλυσης
  • Εισαγωγή ενός νέου μη-τερματικού στη στοιίβα

Αλγόριθμος

1. Ξεκινώντας από τον απλό πίνακα ανάλυσης
2. Σε κάθε θέση (που είναι κενή), με , βάλε την ενέργεια pop
3. Σε κάθε θέση (που είναι κενή), με , βάλε την ενέργεια scan
4. Αν αδειάσει η στοίβα, ενώ δεν έχει ολοκληρωθεί ακόμα η ανάγνωση της συμβολοσειράς εισόδου, εισάγεται στη στοίβα το σύμβολο της αρχής, και αγνοούνται όλα τα επόμενα, μέχρι να αναγνωστεί ένα σύμβολο που να ανήκει στο της αρχής
   Παράδειγμα
   

Εκτέλεση

Παράδειγμα

Ανοδική ΣΑ

• Η συμβολοσειρά εισόδου διαβάζεται από τα αριστερά προς τα δεξιά, και στην πορεία απλοποιείται προς το σύμβολο της αρχής της γραμματικής, με εφαρμογή των κανόνων της
• Το παραγόμενο δέντρο αναπτύσσεται σταδιακά, από τα αριστερά προς τα δεξιά και από τα φύλλα προς τη ρίζα
• Η ανοδική ΣΑ μπορεί να ταυτιστεί με την ανάλυση LR
  Παράδειγμα
  

Ανάλυση LR

Βασικές Έννοιες

• Σε κάθε βήμα της ανοδικής ΣΑ εκτελείται μία από τις εξής Ενέργειες
  1. Απλοποίηση (reduce): σύμφωνα με κάποιον κανόνα της γραμματικής (πχ ) αντικαθιστούνται τα σύμβολα του δεξιού μέρους, από την κορυφή της στοίβας, με το μη-τερματικό του δεξιού
  2. Εισαγωγή Αναγνωιστικού (shift) στη στοίβα της ανάλυσης
  3. Αποδοχή (accept) της συμβολοσειράς εισόδου
• Όταν εκτελείται απολοποίηση με κανόνα- (), τότε το εισάγεται στη στοίβα
• Η ανοδική ΣΑ είναι μία αλληλουχία ενεργειών shift και reduce, μέχρι να εμφανιστέι λάθος, ή να προσεγγιστεί κατάσταση αποδοχής (accept)
• Ενεργό Πρόθεμα: τα σύμβολα που περιέχονται στη στοίβα, σε κάποιο βήμα της εκτέλεσης της ανοδικής ΣΑ
• Λαβή απλοποίησης: μία ακολουθία συμβόλων στην κορυφή της στοίβας, που ταιριάζει στο δεξί μέρος ενός κανόνα, και η εφαρμογή του αποδίδει ένα βήμα δεξιάς παραγωγής
  • Η ταύτιση με το δεξί μέρος κανόνα δεν αρκεί για να είναι μία συμβολοσειρά λαβή
  • Μόνο όταν ο κανόνας δημιουργεί δεξιά παραγωγή με την εφαρμογή του, θεωρούμε τη συμβολοσειρα, λαβή
• Ο κύρια λειτουργία ενός αλγορίθμου ανοδικής ΣΑ, είναι η αναγνώριση της επόμενης λαβής
• Σε μία ανοδική ΣΑ, ο αλγόριθμος μπορεί να βρεθεί σε κατάσταση, που η επόμενη ενέργεια δεν είναι ξεκάθαρη, και πρέπει να επιλαγεί ανάμεσα σε πολλές υποψήφιες
  • Όταν η επιλογή είναι ανάμεσα σε ενέργειες shift και reduce, έχουμε σύγκρουση εισαγωγής-απλοποίησης (shift-reduce conflict)
  • Πιο σπάνια έχουμε και σύγκρουση απλοποίησης-απλοποίησης (reduce-redce conflict)
• Σε περιπτώσεις shift-reduce conflict προτιμάται η shift, χωρίς να είναι εγκυημένα η σωστή απάντηση
• Σε περιπτώσεις reduce-reduce conflict προτιμάται ο πρώτος από τους δύο κανόνες, χωρίς παλι να είναι εγκυημένα ο σωστός

Γενική Λειτουργία

• Παράγεται ο Πίνακας Ενεργειών

  • (Κατάσταση - Επόμενο Σύμβολο) -> Επόμενη Ενέργεια
• Παράγεται ο Πίνακας Μεταβάσεων

  • (Κατάσταση - Σύμβολο) -> Κατάσταση
• Ξεκινάμε με κατάσταση

• Επόμενη Ενέργεια (πιν. Ενεργ.) <-
  πιο δεξιά κατάσταση + επόμενο σύμβολο

• Shift:

  • Προσθέτουμε νέα ρίζα (με όνομα το σύμβολο εισαγωγής)
    • Κατάσταση νέας ρίζας (πίν. Μετ.) <-
      πιο δεξιά κατάσταση + σύμβολο εισαγωγής
• Reduce :

  • νέος κόμβος για το , συνδέεται ως πρόγονος στις πιο δεξιές ρίζες που αντιστοιχούν στο
    • Κατάσταση ρίζας (πιν. Μετ.) <-
      αμέσως αριστ. κατάσταση από συνδεδεμένους κόμβους + σύμβολο εισαγωγής
• Στη στοίβα διατηρείται μαζί με κάθε σύμβολο (ρίζα) και η αντίστοιχη κατάστασή

  • Σε ενέργεια shift, καταχωρείται στην κορυφή της στοίβας, πίσω από το σύμβολο που εισάγεται
  • Σε ενέργεια reduce η λαβή που έχει σχηματιστέι στην κορυφή της στοίβας, αντικαθιστάται αό το μη-τερματικό στο αριστερό μέρος του κανόνα, μαζί με τη νέα κατάσταση
• Είναι απαραίτητη μία λειτουργεία ανάκαμψης από λάθη

Παράδειγμα

Κατασκευή Πινάκων Ανάλυσης LR

Σύνολο Καταστάσεων

• Για κάθε παραλλαγή της ανάλυσης LR πρέπει να υπολογιστεί ένα σύνολο καταστάσεων, από το οποίο προκύπτουν οι πίνακες

LR(0)

• Στοιχείο (Ορισμός)

  • Κάθε στοιχείο του ορίζεται από έναν κανόνα παραγωγής και μία τελεία σε κάποια θέση του δεξιού μέρους του κανόνα, που καταγράφει ένα ενδιάμεσο βήμα στην αναγνώριση των συμβόλων που αυτό περιλαμβάνει
• Έστω ο κανόνας

  • με οποιαδήποτε τερματικά ή μη τερματικά σύμβολα της γραμματικής
• Τα στοιχεία που αναφέρονται στον συγκεκριμένο κανόνα είναι

  • <- αρχικό στοιχείο - τελεία δεξιά
  • <- συμπληρωμένο στοιχείο - τελεία αριστερά
• πχ. το 2ο στοιχείο περιγράγει την κατάσταση που έχει ήδη αναγνωριστεί στην είσοδο, συμβολοσειρά που παράγεται από το και υπάρχει πιθανότητα αναγνώρισης στην είσοδο, συμβολοσειράς που παράγεται από το

• Ο όρος εκφράζει ότι κάθε στοιχείο δεν εξαρτάται από την τιμή κάποιου συμβόλου εισόδου

• Ο κανόνας παράγει το σύνολο με μόνο στοιχείο το

• Ξεκινάμε επεκτείνοντας την γραμματική με ένα κανόνα που ορίζεται ως αρχή της γραμματικής και παίρνει τη μορφή , με την παλιά αρχή της γραμματικής. Μία συμβολοσειρά εισόδου γίνεται αποδεκτή, όταν ο αναλυτής θα μπορούσε να εκτελέσει απλοποίηση για τον κανόνα

• Αντιστοιχίζουμε την αρχική κατάσταση (state 0) το στοιχείο που εκφράζει ότι δεν έχει αναγνωριστεί κάποιο μη-κενό ενεργό πρόθεμα

• Εφαρμόζουμε τους εξής κανόνες για κάθε σύνολο στο εξής:

  • Επέκταση μη-τερματικών (ε-κλείσιμο) : για κάθε στοιχείο (με πριν μη-τερματικό), προσθέτουμε στο ίδιο σύνολο και καθε στοιχείο της μορφής για κάθε κανόνα της μορφής , δηλαδή κάθε κανόνα με το μη-τερματικό στο αριστερό του μέρος, με την στην αρχή
  • Δημιουργία νέων συνόλων (ανάγνωση): για κάθε σύμβολο (τερματικό ή μη) με πριν από αυτό σε κάποιο στοιχείο του συνόλου, δημιούργησε ένα νέο σύνολο, και αρχικοποίησέ το με, βάζοντας την μετά από αυτό, για κάθε στοιχείο που εμφανίζεται
    • Αυτό μπορεί να γραφτεί και ως ά, όπου
      • : το παρόν σύνολο
      • : το σύμβολο που "πυροδώτησε" τη δημιουργία νέου συνόλου
      • : το νέο σύνολο
    • Σημείωσε τις παραπάνω πληροφορίες γιατί θα χρειαστούν αργότερα

Παράδειγμα

• Για να είναι μία γλώσσα είναι αναγκαίο:
  • Να μην υπάρχει σύνολο στοιχείων που περιέχει ταυτόχρονα ένα συμπληρωμένο στοιχείο ( στο τέλος) και ένα στοιχείο της μορφής , με τερματικό
  • Κάθε σύνολο στοιχείων να περιέχει το πολύ ένα συμπληρωμένο στοιχείο